快速排序算法模板
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }；
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
//递归式中j可以替换为i-1，不过需要改变x为x=q[r]，不然死循环
//if (l >= r) return;如果只有一个数则返回
//int i = l - 1, j = r + 1，i和j定义为范围边界往外，是因为先i和j都先++
//此处不能int mid=l+r >>1; 


归并排序算法模板
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)  
        if (q[i] < q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
//temp为合并之后的数组，k表示合并数组中元素的个数  	
//左右区间数组如果有一边已经到达末尾，那么直接输出另一边剩余元素即可

桶排序
for (int i = 1; i <= n; i ++ ) c[s[i]] ++ ;//统计各关键字个数 ps.赋值运算返回左值的引用
for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];//求关键字个数的前缀和
for (int i = n; i; i -- ) sa[c[s[i]] -- ] = i;//倒序：保证排序稳定 每对一个关键字排序对应的c[]--,确定一个数的排名

整数二分算法模板//关键是二段性
bool check(int x) {/* ... */} // 检查x是否满足某种性质,比如大于等于某个数,仅此而已
//二分目的是得到想要的l,注意是l

//区间为int范围内的二分一定要开long long,因为会溢出
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：（注意此时mid时符合条件的）
int bsearch_1(int l, int r)
{
    while (l < r)// '<'
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;           // if语句中r和l的赋值位置不能交换
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;//l+r+1
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}
//循环结束时l和r相等
//假如一段排序好的含有重复元素的序列中，求一个值x的第一个元素位置
//即区间右半边———性质为<=x，的左边界，check（）函数中就是"<=x"的条件
int bsearch_1(int x){
    int l=0;
    int r=n-1;
    while(l<r){
        int mid=(l+r)/2;
        if(a[mid]>=x) r=mid;
        else l=mid+1;
    }
    if(a[l]!=x) return -1;
    return l;
}
//可能数组中没有x无解，但是二分是一定有解的，只需要判断以下二分的解是否等于x即可判断数组是否含有x


浮点数二分算法模板
bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps) //判断浮点数相等:fabs(r-l)<eps
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}
//如果保留6位有效数字，那么eps=1e-8,大2就可以了

如果是小数的话可以不用EPS，直接循环上1000次
三分//求最小值，二次函数
//三分应用于最优化问题的求解。在解题时没必要给出证明，只要知道问题不满足单调性，就可以尝试用三分搜索极值点
//或者如果问题不是二次函数，可以通过枚举干扰项使之成为一个二次函数
double g(double x,double &y)
{
    double l=0,r=100;
    while(r-l>eps)
    {
        double m1=l+(r-l)/3,m2=l+(r-l)/3*2;
        if(f(x,m1)>=f(x,m2)) l=m1;//若为求最大值改为<
        else r=m2;
    }
    y=r;//记录答案
    return f(x,y);
}

整数三分，求max
ll bin3(int l,int r)
{
    if(l>r) return -INF;
    ll res=max(f(l),f(r));//特判端点
    while(l<=r){
        int m=(l+r)>>1,mm=(m+r)>>1;
        ll fm=f(m),fmm=f(mm);
        if(fm<=fmm) l=m+1;
        else r=mm-1;
        res=max(res,max(fm,fmm));
    }
    return res;
}


//读入
string a,b;
vector <int> A,B;
cin >>a>>b;//a = "123456";
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');//A={6,5,4,3,2,1}
for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
//输出
auto C=add(A,B);
for(int i-c.size()-1;i>=0;i--) cout <<c[i];


在涉及小数比较的时候，优先考虑是否可以进行ll比较，避免除法，转化为乘法，或者使用long double
__int128_t 与 __int128 其上界为3.4e38
不能直接输入输出__int128_t类型的数据,输出的时候数据在long long内强制转换就行
或者直接手写函数输出__int128
#define ll __int128//调试完成后
#define ll long long//因为本地不能编译所以调试时用long long
#define int long long //使用前需要将主函数改为signed main()
inline ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
         f=-1;
         ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

inline void write(ll x)
{
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9){
        write(x/10);
    }
    putchar(x%10+'0');
}
同理long double 与 double ,有的oj不支持long double 那么运算时用long double 输出时强制转换为double 



高精度加法
// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}
//t表示进位
//if (t) C.push_back(t);表示A,B最高位的下一位有进位的话需要添加一个1


bool cmp(vector<int> &A,vector<int> &B){
	if(A.size()!=B.size()) return A.size() >B.size();
	for(int i=A.size()-1;i>=0;i--){
		if(A[i]!=B[i]) return A[i]>B[i];
	}
	return true;//表示A=B
}
if(cmp(A,B)){//A>=B
	auto C=sub(A,B);
	for(int i=C.size()-1;i>=0;i--) cout <<c[i];
}else{//B>A,那么A-B为一个负数
	auto C=sub(B,A);
	cout <<"-";
	for(int i=C.size()-1;i>=0;i--) cout <<c[i];
}

高精度减法
// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
//如果A<B,那么结果为-sub（B,A）
//t为借位，借位即为1
//A[i]-B[i]-t大于等于0，则不变，如果小于0借位，那么A[i]-B[i]-t+10
//C.push_back((t + 10) % 10);将上面一句的两种情况合二为一了
//最后还需要去除前导零，但是只有一个0就不需要了


高精度乘低精度
// C = A * b, A >= 0, b > 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}
//将b看作一个整体来乘A的每一位


高精度除以低精度
// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
//r为余数  


一维前缀和
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]


二维前缀和
S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
//二维前缀和的初始化
//for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+a[i][j];
//内存如有限制那么可以省略a数组，直接先s数组累加

//下标从0开始的S数组
/*for (int i = 0; i < N; i ++ )
    for (int j = 0; j < N; j ++ )
    {
        if (i) s[i][j] += s[i - 1][j];
        if (j) s[i][j] += s[i][j - 1];
        if (i && j) s[i][j] -= s[i - 1][j - 1];
    }*/

一维差分
给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c
//一维差分数组的初始化，假设A数组全体为0，相当于在在i位与i位间加入A[i]
//void insert(int l,int r,int c){
	B[l]+=c;
	B[r+1]-=c;
}
//for(int i=1;i<=n;i++) insert(i,i,A[i]);

二维差分
给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c
//S[x1,y1]+=c，指的是x1，y1到右下角全体元素都加c
//差分数组S初始操作同上，先假设a[i][j]都是0，然后插入一个左上角是i，j
//后下角也是i，j值为a[i][j]的元素
//void insert(int x1,int y1,int x2,int y2,int c){
	B[x1][y1]+=c;
	B[x2+1][y1]-=c;
	B[x1][y2+1]-=c;
	B[x2+1][y2+1]+=c;
}
//for(int i=1;i<=n;i++) for(itn j=1;j<=m;j++) insert(i,j,i,j,a[i][j]);
//对差分求前缀和 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];


位运算
求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n

二进制枚举
for(int i=0;i<(1<<n);i++)
    for(int j=0;j<n;j++)
        if((i>>j)&1) ...

双指针算法//O(n)
for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;//不一定是j<i,也可能是i为左端点j为右端点

    // 具体问题的逻辑
}
常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作


离散化//当题目涉及的数据范围很大，但是用到的范围很小时使用，下面是保序的写法
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}

int find(double y)
{
    return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}

//将每个数的离散值预处理出来
for(int i=1;i<=n;i++){
    cin >>a[i];
    id[i]=a[i];
}
sort(id+1,id+1+n);
int siz=unique(id+1,id+1+n)-id;
for(int i=1;i<=n;i++)
    a[i]=lower_bound(id+1,id+siz+1,a[i])-id;


//离散化不保序则可以使用map,hash(unordered_map)
//map平均复杂度是O(logN),但是unordered_map复杂度是O(1)。前者封装红黑树，后者封装Hash
int n=0;
unordered_map<int,int> S;
int get(int x)
{
    if(S.count(x)==0) S[x]=++n;//不在hash表中则分配一个值
    return S[x];
}
//x映射为get(x)

区间合并//时间复杂度O(mlogm),m为需合并的区间数
// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);

    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}
//初始维护数组边界定义为负无穷，循环时分为有无交集两种情况
//if (st != -2e9) res.push_back({st, ed});
//是为了防止空区间而且将得到的最后一个区间加入res

//一个小tip：当原区间的最小坐标为x时，可以初始化L=x,R=x-1，此时的区间长度为0（R-L+1）


set维护区间合并
for (int i = 1; i <= n; ++i) {
    s.insert({i, i});//先将单独的各点插入
}
for (int i = 1; i <= m; ++i) {//m次合并，每次合并l-r的区间
    int l = v[i - 1].l, r = v[i - 1].r;
    auto p = --s.upper_bound({l + 1, 0});
    vector<pair<int, int>> del;
    while (p != s.end() && p->first <= r) {
        del.push_back(*p);
        p++;
    }
    for (auto pii: del) s.erase(pii);//删除set中应该合并的区间
    l = del[0].first, r = del.back().second;
    s.insert({l, r});//添加合并后的区间
}


求被n个区间包含的数的个数
//sol中存储的是区间的左右端点
vector<PII> res;
for(int i=0;i<sol.size();i++)
{
    res.push_back({sol[i].x,1});
    res.push_back({sol[i].y+1,-1});
}
sort(res.begin(),res.end());

int dep=0,ans=0;
for(int i=0;i<res.size();i++)
{
    dep+=res[i].y;
    if(dep==n)
        if(i+1<res.size())
            ans+=res[i+1].x-res[i].x;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int m, n;
struct Segment
{
    int l, r;
    bool operator< (const Segment& t) const
    {
        return l < t.l;
    }
}seg[N];

int main()
{
    cin >> m >> n;
    for (int i = 0; i < n; i ++ ) cin >> seg[i].l >> seg[i].r;
    sort(seg, seg + n);

    int sum = 0;
    int L = seg[0].l, R = seg[0].r;
    for (int i = 1; i < n; i ++ )
        if (seg[i].l <= R) R = max(R, seg[i].r);
        else
        {
            sum += R - L + 1;
            L = seg[i].l, R = seg[i].r;
        }
    sum += R - L + 1;
    cout << m + 1 - sum << endl;

    return 0;
}

随机数
#include <iostream>
#include <ctime>
using namespace std;
int main()
{
    srand(unsigned(time(0)));
    int count = rand() % 3 + 1;    //范围1~3
    int count1 = rand() % 3;    //范围0~2
    cout << count << endl << count1 << endl;
    return 0;
}
此时随机数最大值RAND_MAX为32767
double rand(double l,double r)//随机l-r之间的浮点数
{
    return (double)rand()/RAND_MAX*(r-l)+l;
}

mt19937 mrand(time(0));
int num=mrand()%n;

无范围：
#include <iostream>
#include <chrono>
#include <random>
using namespace std;
int main()
{
    // 随机数种子
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    mt19937 rand_num(seed);  // 大随机数
    cout << rand_num() << endl;
    return 0;
}

有范围：
#include <iostream>
#include <chrono>
#include <random>
using namespace std;
int main()
{
    // 随机数种子
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    mt19937 rand_num(seed);  // 大随机数
    uniform_int_distribution<long long> dist(0, 1000000000);  // 给定范围
    cout << dist(rand_num) << endl;
    return 0;
}

template <class T>
T randint(T l, T r = 0) // 生成随机数建议用<random>里的引擎和分布，而不是rand()模数，那样保证是均匀分布
{
    static mt19937 eng(time(0));
    if (l > r)
        swap(l, r);
    uniform_int_distribution<T> dis(l, r);
    return dis(eng);
}
x = randint(2, n - 1); // 生成2和n-1之间的随机数

4MB————1e6in

一般ACM或者笔试题的时间限制是1秒或2秒。

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

n≤30, 指数级别, dfs+剪枝，状态压缩dp
n≤100 => O(n3)O(n3)，floyd，dp，高斯消元
n≤1000 => O(n2)O(n2)，O(n2logn)，dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
n≤10000 => O(n∗n√)O(n∗n)，块状链表、分块、莫队
n≤100000 => O(nlogn)O(nlogn) => 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分
n≤1000000 => O(n)O(n), 以及常数较小的 O(nlogn) 算法 => 单调队列、 hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 O(nlogn)O(nlogn) 的做法：sort、树状数组、heap、dijkstra、spfa
n≤10000000 => O(n)O(n)，双指针扫描、kmp、AC自动机、线性筛素数
n≤10^9 => O(n√)O(n)，判断质数
n≤10^18 => O(logn)O(logn)，最大公约数，快速幂
n≤10^1000 => O((logn)2)O((logn)2)，高精度加减乘除
n≤10^100000 => O(logk×loglogk)，k表示位数，k表示位数，高精度加减、FFT/NTT

#include<bits/stdc++.h>

using namespace std;

int main()
{
    while(true)
    {
        system("data.exe>data.in");//data.exe输出数据到data.in
        system("ac.exe<data.in>ac.out");//ac.exe由data.in输入数据输出数据到ac.out
        system("wa.exe<data.in>wa.out");
        if(system("fc ac.out wa.out"))//fc为比较函数
        {
            system("pause");
        }
    }

}

特殊读取字符串
int t;
cin >>t;
getline(cin, tmp);//多余空格换行读入
string tmp;
getline(cin, tmp);
stringstream ssin(tmp);
vector<string> hh;
while (ssin >> tmp) hh.push_back(tmp);


交互题：//通常都是跟二分三分有关，或者自己推导规律
每次询问，你需要向标准输出输出一个结果，然后清空缓冲区。
你可以使用如下语句来清空缓冲区：
对于 C/C++：fflush(stdout)；
对于 C++：std::cout << std::flush；
特别的，对于 C++ 语言，在输出换行时如果你使用 std::endl 而不是 '\n'，也可以自动刷新缓冲区。
//在代码中的回答方式就是会输入某个东西就是系统给你的答案

参考程序：
评测机会在区间 [1,10^9]中选择一个整数，你应该写一个代码来猜测它。你最多可以问评测机 50 个问题。
对于每一次询问，你可以向评测机询问区间 [1,10^9]中的一个整数，评测机会返回:
0，如果它为答案（即评测机所选的数字），且程序应该在此之后停止询问。
-1，如果它小于答案。
1，如果它大于答案。
#include <cstdio>
#include <iostream>

int main() {
  for (int l = 1, r = 1000000000, mid = (l + r) >> 1, res; l <= r; mid = (l + r) >> 1) {
    std::cout << mid << std::endl;
    std::cin >> res;
    if (res == 0) {
      return 0;
    } else if (res == -1) {
      l = mid + 1;
    } else if (res == 1) {
      r = mid - 1;
    }
  }
  return 0;
}

还有一种是通过调用交互库提供的函数
你的答案应该作为函数的返回值给出，你不需要，也不应该向标准输出输出任何内容
#include<cstdio>//如果您需要头文件，那么可以像普通程序一样在程序开头包含这些头文件

extern "C" int Seniorious(int);//交互库提供的函数请在程序开头声明定义

extern "C" int Chtholly(int n, int OvO)//题目需要实现的函数请在程序里进行实现
{
    return 0;//这里只是一个例子，具体内容请自行实现
}

标程：
extern "C" int Seniorious(int);

extern "C" int Chtholly(int n, int OvO)
{
    int l=1,r=n;
    while(r>l)
    {
        int mid=(l+r)/2;
        int res=Seniorious(mid);
        if(res==0)return mid;
        if(res==1)r=mid-1;
        else l=mid+1;
    }
    return l;
}


快读
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}

template <typename T>
inline T
read() {  // 声明 template 类,要求提供输入的类型T,并以此类型定义内联函数 read()
  T sum = 0, fl = 1;  // 将 sum,fl 和 ch 以输入的类型定义
  int ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') fl = -1;
  for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
  return sum * fl;
}
a = read<int>();
b = read<long long>();
c = read<__int128>();


namespace IO{
    #define BUF_SIZE 100000
    #define OUT_SIZE 100000
    #define ll long long
    //fread->read
    bool IOerror=0;
    inline char nc(){
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if (p1==pend){
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if (pend==p1){IOerror=1;return -1;}
            //{printf("IO error!\n");system("pause");for (;;);exit(0);}
        }
        return *p1++;
    }
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline void read(int &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    inline void read(ll &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    inline void read(double &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (ch=='.'){
            double tmp=1; ch=nc();
            for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
        }
        if (sign)x=-x;
    }
    inline void read(char *s){
        char ch=nc();
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
        *s=0;
    }
    inline void read(char &c){
        for (c=nc();blank(c);c=nc());
        if (IOerror){c=-1;return;}
    }
    struct Ostream_fwrite{
        char *buf,*p1,*pend;
        Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
        void out(char ch){
            if (p1==pend){
                fwrite(buf,1,BUF_SIZE,stdout);p1=buf;
            }
            *p1++=ch;
        }
        void print(int x){
            static char s[15],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1);
        }
        void println(int x){
            static char s[15],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1); out('\n');
        }
        void print(ll x){
            static char s[25],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1);
        }
        void println(ll x){
            static char s[25],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1); out('\n');
        }
        void print(double x,int y){
            static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,
                1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,
                100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
            if (x<-1e-12)out('-'),x=-x;x*=mul[y];
            ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1;
            ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2);
            if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i); print(x3);}
        }
        void println(double x,int y){print(x,y);out('\n');}
        void print(char *s){while (*s)out(*s++);}
        void println(char *s){while (*s)out(*s++);out('\n');}
        void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
        ~Ostream_fwrite(){flush();}
    }Ostream;
    inline void print(int x){Ostream.print(x);}
    inline void println(int x){Ostream.println(x);}
    inline void print(char x){Ostream.out(x);}
    inline void println(char x){Ostream.out(x);Ostream.out('\n');}
    inline void print(ll x){Ostream.print(x);}
    inline void println(ll x){Ostream.println(x);}
    inline void print(double x,int y){Ostream.print(x,y);}
    inline void println(double x,int y){Ostream.println(x,y);}
    inline void print(char *s){Ostream.print(s);}
    inline void println(char *s){Ostream.println(s);}
    inline void println(){Ostream.out('\n');}
    inline void flush(){Ostream.flush();}
    #undef ll
    #undef OUT_SIZE
    #undef BUF_SIZE
};
输入输出形式
IO::read(t);
IO::println(t);


对拍程序
#include<bits/stdc++.h>

using namespace std;

int main()
{
    while(true)
    {
        system("data.exe>data.in");//data.exe输出数据到data.in
        system("ac.exe<data.in>ac.out");//ac.exe由data.in输入数据输出数据到ac.out
        system("wa.exe<data.in>wa.out");
        if(system("fc ac.out wa.out"))//fc为比较函数
        {
            cout <<"data.in:\n";
            system("type data.in");
            system("pause");
        }
    }
}

linux下shell脚本
while true;do
./rand>in.txt
./sta<in.txt>sta_out.txt
./test<in.txt>test_out.txt
if diff sta_out.txt test_out.txt;then
printf "AC\n"
else 
printf "\nWA\n\n\n"
printf "data in:\n"
cat in.txt
printf "\nsta_output: \n"
cat sta_out.txt
printf "\ntest_output: \n" 
cat test_out.txt
exit 0
fi
done
#终端下，进入当前目录，输入"sh ./duipai.sh"(其中duipai是脚本名称)


模拟退火
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<double,double> PDD;
const int N=110;

int n;
PDD q[N];
double ans=1e8;

double rand(double l,double r)
{
    return (double)rand()/RAND_MAX*(r-l)+l;
}

double get_dist(PDD a,PDD b)
{
    double dx=a.x-b.x;
    double dy=a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}

double calc(PDD p)
{
    double res=0;
    for(int i=0;i<n;i++)
        res+=get_dist(p,q[i]);
    ans=min(ans,res);
    return res;
}

void simulate_anneal()
{
    PDD cur(rand(0,10000),rand(0,10000));//当前点
    for(double t=1e4;t>1e-3;t*=0.99)//温度衰减过程
    {
        PDD np(rand(cur.x-t,cur.x+t),rand(cur.y-t,cur.y+t));//新点
        double dt=calc(np)-calc(cur);
        if(exp(-dt/t)>rand(0,1)) cur=np;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >>n;
    for(int i=0;i<n;i++)
        cin >>q[i].x>>q[i].y;

    for(int i=0;i<100;i++)
        simulate_anneal();

    cout <<round(ans)<<endl;

    return 0;
}
